[Previous] [Next] [Index] [Thread]

Re: Netscape's purported RNG

On Sep 22,  9:39, Jeffrey I. Schiller wrote:
> Turns out you cannot do this for security, or more specifically for testing
> cryptographic algorithms and for analyzing random number generators.
> 
> A random number generator can generate output that passes any and all
> statistical tests for randomness, but is still completely predictable to
> someone who knows how it works internally. The only solution is to have the
> code both examined and tested by experts in the field. There are few such
> experts in this field.

Yep. Here's a copy of a post I just did to ssl-talk.

================== POSTED TO SSL-TALK LIST =================
[PRNG = Pseudorandom Number Generator]

Several posts back I wrote:
>>> PRNGs are useful for statistics, they are basically worthless 
>>> for cryptography. 

On Sep 22, 12:07, Roy Badami wrote:
> [...] The point is that you can't generate a 128-bit random number by 
> calling a 32-bit PRNG four times, unless that PRNG has at least 
> 128-bits worth of internal state.  

Then it is a 128-bit PRNG, not a 32-bit one.

> If the PRNG only has 32-bits 
> of internal state, then your 128-bit pseudo-random number is 
> limited to 2^32 possible values, and you've effectively reduced 
> the search space from 128 bits to 32 bits.

Right!!! Once you "start" the PRNG with the 128-bit initial internal state, 
everything it emits thereafter is predictable! So once you consume 128 bits 
from the PRNG output, the entropy available has dropped to 0. It is exactly 
the same point you make about trying to use a 32-bit PRNG 4 times to get 128 
bits. Trying to use a 128-bit PRNG more than once is a waste of time.

> The PRNG must, of course, be cryptographically strong, to ensure that future 
> outputs can't be predicted from earlier ones.

Huh? The output of a PRNG is deterministic, given the seed. That's why it is 
called a "pseudo" random number generator.  

> A simple solution is to 
> DES-encrypt a conventional PRNG with a truely random key.

Truly random key? How big? And how many truly random bits do you need? Turns 
out you need that many bits for the DES encryption if you want that many bits 
entropy.

I repeat my point. There's no such thing as a free lunch. However many truly 
random bits you need, that's how many truely random bits you need. There's no 
way to "amplify" the randomness of some random data by using PRNGs or whatever 
(according to the theoretical framework as we know it).

What you _can_ (and should) do is "whiten" (as in white noise from comm. 
theory) the truly random input data somehow. The system used in WebSite uses a 
large pool of random numbers that is "stirred" via an MD5/CFB process each 
time some new truly random noise is added. The idea is to make all of the bits 
in the pool depend on the newly added noise. Other systems are possible.

I must thank Colin Plumb for setting me straight on all of this last year. He 
was an invaluable mentor.

  -- Bob
References: